package com.jack.leetcode.每日一题;

/*** 
 * @author zhangjie
 * @date 2020/5/6 20:03
 */
public class 最低票价 {

    public int mincostTickets(int[] days, int[] costs) {
        int l = days.length;
        int[] dp = new int[days[l - 1] + 31];
        for (int i = l - 1; i >= 0; i--) {
            int index = days[i];
            int min = Math.min(costs[0] + dp[index + 1], costs[1] + dp[index + 7]);
            dp[index] = Math.min(min, costs[2] + dp[index + 30]);
            if (i > 0) {
                for (int j = days[i - 1] + 1; j < index; j++) {
                    dp[j] = dp[index];
                }
            }
        }
        return dp[days[0]];
    }
}
